package com.iran;

import java.util.Arrays;

/**
 * 实现堆排序需要解决两个问题：
 *
 * 　　　　1.如何由一个无序序列建成一个堆？
 *
 * 　　　　2.如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？
 *
 * 　　先考虑第二个问题，一般在输出堆顶元素之后，视为将这个元素排除，然后用表中最后一个元素填补它的位置，自上向下进行调整：首先将堆顶元素和它的左右子树的根结点进行比较，把最小的元素交换到堆顶；然后顺着被破坏的路径一路调整下去，直至叶子结点，就得到新的堆。
 *
 * 　　我们称这个自堆顶至叶子的调整过程为“筛选”。
 *
 * 　　从无序序列建立堆的过程就是一个反复“筛选”的过程。
 */
public class HeapSortMax {
    static int[] arr;
    public static void main(String[] args) {
        HeapSortMax heapSor = new HeapSortMax();
        int[] arr = {0,23,45,9,40,73,12,49,423,122,33,44,55,66,77,88,99,101,102,133,144};//第0位代表数组长度
        arr[0] = arr.length-1;
        heapSor.arr = arr;
        heapSort(arr);
    }
    static void heapSort(int[] arr){
        //对数组进行建堆操作，就是从最后一个非叶节点进行筛选
        for(int i = (arr.length-1)/2;i>0;i--){
            heapAdjust(arr,i,arr.length-1);
        }
        System.out.println("建堆完成");
        //Arrays.stream(arr).forEach(System.out::println);
        //outputArr(1);\
        int count = 1;
        for (int i = arr.length-1;i>1;i--){
            //根节点
            int temp = arr[1];
            arr[1]=arr[i];
            arr[i]=temp;
            heapAdjust(arr,1,i-1);
            if (i == (arr.length-1-4+1)){
                break;
            }
        }
        System.out.println("调整完成");
        Arrays.stream(arr).forEach(System.out::println);
    }
    static void heapAdjust(int[] arr,int s,int m){
        int rc = arr[s];//最后一个非叶子节点
        for(int j =2*s;j<=m;j=s*2){
            //若子节点不是最后一位且其小于其右侧节点则使用其右侧节点
            if (j<m&&arr[j]<arr[j+1]){
                j++;
            }
            //若其父节点值大于等于其最大子节点值则满足大顶堆规则
            if (rc >=arr[j]){
                break;
            }
            //上述两个判断都没进入，则子节点需要上移到其父节点
            arr[s]=arr[j];
            s=j;
        }
        arr[s]=rc;//原子节点值等于原父节点值
    }
    static void outputArr(int i){
        if (i<=arr[0]){
            System.out.println(arr[i]);
            outputArr(i*2);
            outputArr(i*2+1);
        }
    }
}
